import java.util.*;

/**
 * @author LKQ
 * @date 2022/5/10 10:20
 * @description 动态规划 将问题抽象为多维背包问题，每个任务可以看作为一个物品，消耗的人员为成本，获得的利润为价值，
 */
public class Solution {
    public static void main(String[] args) {

    }
    int mod = (int)1e9+7;
    public int profitableSchemes(int n, int min, int[] gs, int[] ps) {
        int m = gs.length;
        // f[i][j][k] 代表考虑前 i 个任务，使用人数不超过 j，产生利益至少 k 的方案数
        int[][][] f = new int[m+1][n+1][min+1];
        // 初始化：当没有任务时，无论有多少人，只有利益至少为 0 时的方案数为 1，其他为 0
        for (int j = 0; j <= n; j++) {
            f[0][j][0] = 1;
        }
        for (int i = 1; i <= m; i++) {
            int g = gs[i-1], p = ps[i-1];
            for (int j = 0; j <= n; j++) {
                for (int k = 0; k <= min; k++) {
                    f[i][j][k] = f[i-1][j][k];
                    if (j >= g) {
                        f[i][j][k] += f[i-1][j-g][Math.max(0, k-p)];
                        f[i][j][k] %= mod;
                    }
                }
            }
        }
        return f[m][n][min];
    }
}
